package 回溯

/*
https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-100-liked

46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]
*/
var (
	res  [][]int
	path []int
	used []bool
)

func permute(nums []int) [][]int {
	res = make([][]int, 0)
	path = make([]int, 0)
	used = make([]bool, len(nums))

	dfs(nums, 0) //调用递归方法
	return res
}
func dfs(nums []int, cur int) {
	if cur == len(nums) { //如果当前位置已经到达参数数组最后一位, 收集结果
		temp := make([]int, len(path))
		copy(temp, path)
		res = append(res, temp)

		return
	}
	//单层遍历
	for i := 0; i < len(nums); i++ { //从0号位置开始
		if !used[i] {
			path = append(path, nums[i])
			used[i] = true
			dfs(nums, cur+1)
			used[i] = false
			path = path[:len(path)-1]
		}
	}
}
